package com.demo132_分割回文串2;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int partition(String s) {
        int time=0;
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        if (s==null){
            return time;
        }
        if (s.length()==0){
            return time;
        }

        //特判: 如果整体是对称的,直接返回0
        if (check(s)){
            return 0;
        }
        dfs(s,result,path,0);


        time=result.get(0).size();
        for (List<String> list : result) {
            time=Math.min(list.size(),time);
        }

        return time-1;
    }

    private void dfs(String s, List<List<String>> result, List<String> path, int startIndex) {
        //1.边界条件
        if (startIndex==s.length()){
            ArrayList<String> copy = new ArrayList<>();
            for (String s1 : path) {
                copy.add(s1);
            }
            result.add(copy);
            return;
        }     //  (int)Math.ceil(((startIndex+s.length())/2 )+ 1) :  当这个遍历超过一半时,   但是这种情况没有考虑到: abccbaf  这种情况,需要1次
        //2.横向遍历: 剪枝
        for (int i = startIndex; i <s.length(); i++) {

            if (check(s.substring(startIndex,i+1))){
                //3.处理结果
                path.add(s.substring(startIndex,i+1));
                //4.纵向遍历
                dfs(s,result,path,i+1); // 这里纵向遍历的时候要注意: 是 i+1, 不是 startIndex +1
                //5.回溯
                path.remove(path.size()-1);
            }

        }
    }

    //辅助函数判断是否是回文串
    public boolean check(String s){
        if (s!=null&&s.length()!=0){
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i)!=s.charAt(s.length()-1-i)&&i<=(s.length()-i)){
                    return false;
                }
            }
            return true;
        }
        return false;
    }
}
